package Array;

import org.junit.Test;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Array
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-18  22:37
 * @Description: TODO
 * @Version: 1.0
 */
public class 跳跃游戏II45 {

    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            // 维护当前能够到达的最大下标位置
            maxPosition = Math.max(maxPosition, i + nums[i]);
            // 到达边界时，更新边界并将跳跃次数增加 1
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    public int jump2(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;

        while (position > 0) {
            // 从左边开始遍历
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    @Test
    public void test(){
        int jump = jump(new int[]{2, 3, 1, 1, 4});
        System.out.println(jump);
    }
}
